// “这个地方的所有房屋的排列类似于一棵二叉树”。 
// 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

// 输入: [3,2,3,null,3,null,1]

//      3
//     / \
//    2   3
//     \   \ 
//      3   1

// 输出: 7 
// 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 暴力法：爷+孙子节点值 vs 两个孩子节点值 --- 超时
// int rob(struct TreeNode* root){
//     if (root == NULL) return 0;
//     int res = root->val;
//     if (root->left) {
//         res += (rob(root->left->left) + rob(root->left->right)); //左孙子
//     } 
//     if (root->right) {
//         res += (rob(root->right->left) + rob(root->right->right)); //右孙子
//     }
//     return fmax(res, rob(root->left) + rob(root->right)); 
// }


// 动态规划：
// 当前节点选择不偷：当前节点能偷到的最大钱数 = 左孩子能偷到的钱 + 右孩子能偷到的钱
// 当前节点选择偷：当前节点能偷到的最大钱数 = 左孩子选择自己不偷时能得到的钱 + 右孩子选择不偷时能得到的钱 + 当前节点的钱数
void rob1(struct TreeNode* root, int *res0, int *res1) {
    if (root == NULL) {
        *res0 = 0; *res1 = 0;
        return ;
    }
    int left[2], right[2];
    rob1(root->left, &left[0], &left[1]);
    rob1(root->right, &right[0], &right[1]);

    // 当前节点不偷：res0 = lmoney + rmoney;
    // 当前节点要偷：res1 = val + lmoney.res0 + rmoney.res0
    *res0 = fmax(left[0], left[1]) + fmax(right[0], right[1]);   
    *res1 = root->val + left[0] +right[0];  
}

int rob(struct TreeNode* root){
    int res0, res1;
    rob1(root, &res0, &res1); 
    return fmax(res0, res1);
}












